package leetcode;
/**
 * 876.链表的中间节点
 * 给定一个头结点为 head 的非空单链表，返回链表的中间结点。
 * 如果有两个中间结点，则返回第二个中间结点。
 * 输入：[1,2,3,4,5]
 * 输出：此列表中的结点 3
 * 输入：[1,2,3,4,5,6]
 * 输出：此列表中的结点 4
 */
public class Num_876 {
    //快慢指针法
    public ListNode middleNode(ListNode head) {
        //fast一次走两步
        //low一次走一步
        //当fast走到 尾节点 or 尾节点的下一位 时，low刚好处于中间节点
        ListNode fast = head;
        ListNode low = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            low = low.next;
        }
        return low;
    }
}
